package algorithmic_data_structure.动态规划;

import java.util.PriorityQueue;

// 题目
// 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
// 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
// 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
// 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
// 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
// 四个参数：arr, n, a, b
// 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
public class 咖啡杯问题 {
    static class CoffeeMachine {
        int freeStart;
        int workTime;
    }

    public static int minTime1(int[] arr, int n, int a, int b) {
        CoffeeMachine[] coffeeMachines = new CoffeeMachine[arr.length];
        PriorityQueue<CoffeeMachine> minHeap = new PriorityQueue<>((w1, w2) -> (w2.freeStart + w2.workTime) - (w1.freeStart + w1.workTime));
        for (int i = 0; i < arr.length; i++) {
            coffeeMachines[i] = new CoffeeMachine();
            coffeeMachines[i].freeStart = 0;
            coffeeMachines[i].workTime = arr[i];
            minHeap.add(coffeeMachines[i]);
        }
        int[] drinks = new int[n];//每个人喝到coffer的时候
        for (int i = 0; i < n; i++) {
            CoffeeMachine poll = minHeap.poll();
            drinks[i] = poll.freeStart + poll.workTime;
            poll.freeStart = drinks[i];
            minHeap.add(poll);
        }
//        return process(drinks,a,b,0,0);
        return processDP(drinks, a, b);
    }

    /**
     * @param drinks   每个人喝到coffee的时候，喝到即喝完
     * @param a        洗一个杯子的时间
     * @param b        挥发一个杯子的时间
     * @param index    轮到哪一个人喝
     * @param freeTime 洗coffee机空闲的时间点
     * @return
     */
    private static int process(int[] drinks, int a, int b, int index, int freeTime) {
        if (drinks.length == index) {
            return 0;
        }
        //选择洗coffee机,需要等待的时间
        int clean1 = Math.max(drinks[index], freeTime) + a;
        int restClean1 = process(drinks, a, b, index + 1, clean1);
        int ans1 = Math.max(clean1, restClean1);//其实是不知道谁比较大的，需要比较一下
        //选择自然挥发 需要等待的时间;洗coffee机时间保持不变
        int clean2 = drinks[index] + b;
        int restClean2 = process(drinks, a, b, index + 1, freeTime);
        int ans2 = Math.max(clean2, restClean2);
        return Math.min(ans1, ans2);
    }

    private static int processDP(int[] drinks, int a, int b) {
        int maxFree = 0;//如果一直用洗coffee机需要的最大时间
        for (int i = 0; i < drinks.length; i++) {
            maxFree = Math.max(maxFree, drinks[i]) + a;
        }
        int[][] dp = new int[drinks.length + 1][maxFree + 1];

        for (int index = drinks.length - 1; index >= 0; index--) {
            for (int free = 0; free <= maxFree; free++) {
                //选择洗coffee机,需要等待的时间
                int clean1 = Math.max(drinks[index], free) + a;
                if (clean1 > maxFree) {
                    break;
                }
//                int restClean1 = process(drinks,a,b,index+1,clean1);
                int restClean1 = dp[index + 1][clean1];
                int ans1 = Math.max(clean1, restClean1);//其实是不知道谁比较大的，需要比较一下
                //选择自然挥发 需要等待的时间;洗coffee机时间保持不变
                int clean2 = drinks[index] + b;//dp数组不涉及clean2，所以可以说clean2是没有界限的
//                int restClean2 = process(drinks,a,b,index+1,freeTime);
                int restClean2 = dp[index + 1][free];
                int ans2 = Math.max(clean2, restClean2);
                dp[index][free] = Math.min(ans1, ans2);
            }
        }
        return dp[0][0];
    }
}
